﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using TiposComuns.Objectos;

namespace Pesquisa
{
    /// <summary>
    /// Tree of k-buckets for the kademlia algorithm.
    /// Each branch contains, on the left side, all the
    /// nodes that have the nth bit to 0 of their username's hash,
    /// where n is the level of the tree. The right side contains the nodes
    /// with the same bit set to 1.
    /// </summary>
    public class KTree
    {
        #region Attributes
        public KTree left;       //List of nodes with the nth bit set to 0
        public KTree right;      //Tree of nodes with the nth bit set to 1
        public KTree father;     //Upper level of the tree
        public KBucket bucket;   //List of nodes located on the leaf of this tree
        Person person;
        #endregion

        #region Constructors
        public KTree(Person person)
        {
            this.bucket = new KBucket();
            this.bucket.IsCont = true;
            this.person = person;
        }

        /// <summary>
        /// Initializes the tree with an existent k-bucket
        /// </summary>
        /// <param name="bucket">K-bucket</param>
        public KTree(Person person, KTree father, KBucket bucket)
        {
            this.father = father;
            this.bucket = bucket;
            this.person = person;
        }
        
        #endregion
        
        #region Methods

        /// <summary>
        /// Returns the tree where the element should be inserted, by analising
        /// bit by bit, the hash, from the most significative bit to the least significative
        /// </summary>
        /// <param name="hash">Hash</param>
        /// <returns>Tree</returns>
        private KTree GetTree(byte[] hash)
        {
            KTree iter = this;                  //Starts with the current tree

            int order = HashService.NBITS-1;    /*Current bit, starting from 0 to NBITS-1, from right to left
                                                 * This means that the order of bit most significative bit is NBITS-1.
                                                 * So, we start from the most significative bit, and walk to the least
                                                 *significative
                                                 */

            byte mask = 0x80;                   /*One bit mask for isolating the current bit.
                                                 *Starts with the most significative bit set to one and
                                                 *decreases to 1. Once it reaches 1, if the hash has still more bytes,
                                                 *we need to restart it with the value 0x80 or 128
                                                 */

            bool bit = ((mask & hash[0])!=0);   // Current bit
                                                 

            bool parar = (iter.bucket.Bit == bit) 
                || (iter.left==null && iter.right==null);   
                                              /* Determines if we should stop traversing the hash.
                                               */

            int i = 0;
            
            while (!parar)                  //Traverses the tree and the bits of the hash
            {
                iter = (bit) ? iter.right : iter.left;      //If bit==1, go to right, else go to left
                order--;                                    

                i += (mask > 1) ? 0 : 1;                    /* If mask==1, it means that we have to jump to another
                                                             * hash's byte and to restart the mask with the value 0x80,
                                                             * or 128.
                                                             */
                mask = (byte)((mask > 1) ? (mask >> 1) : 0x80);

                bit = ((mask & hash[i]) != 0);

                parar = (iter.bucket.Bit == bit)
                || (iter.left == null && iter.right == null);   
            }

            return iter;
        }

        /// <summary>
        /// Adds a new node to the tree
        /// </summary>
        /// <param name="person">New node</param>
        /// <returns>Success of the operation</returns>
        public bool Add(Person person)
        {
            KTree iter = this.GetTree(person.Hash);         //Obtains the subtree where the new element should be inserted
            bool result = false;                            //Result of the insertion

            if (iter.bucket.Count()< KBucket.K)             //If k-bucket isn't full
            {
                result = iter.bucket.Add(person);
            }
            else if(iter.bucket.IsCont)                     
            {
                /*If k-bucket is full and host hash is contained there
                 * we split the current k-bucket
                 */

                

                KBucket aux = iter.bucket.Split();          /* Split the k-bucket iter.bucket.
                                                             * aux contains the hashes wich current bit is 1
                                                             * and iter.bucket the other ones
                                                             */

                iter.bucket.IsCont = 
                    (this.person.GetBit(iter.bucket.Order) == 0); /* The host hash is contained
                                                                        * on iter.bucket if it's current
                                                                        * bit is 0, otherwise it's contained
                                                                        * on aux.
                                                                        */

                aux.IsCont = !iter.bucket.IsCont;

                int order = person.GetBit(iter.bucket.Order);

                result = (order == 1) ? 
                    aux.Add(person) : iter.bucket.Add(person);      //Adds the new node
                

                /* We allways keep the k-bucket where the host isn't contained
                 * in the upper levels of the tree. Higher the level, 
                 * greater the distance to the host's hash.
                 */
                if (aux.IsCont)
                {
                    iter.right = new KTree(this.person, iter, aux);
                }
                else
                {
                    iter.left = new KTree(this.person, iter, iter.bucket);
                    iter.bucket = aux;
                }                
            }

            return result;
        }
        

        /// <summary>
        /// Returns the k-bucket to wich the person should belong
        /// and the corresponding bit order
        /// </summary>
        /// <param name="person">Person</param>
        /// <returns>K-bucket</returns>
        public KBucket GetKBucket(Person person)
        {
            return this.GetTree(person.Hash).bucket;            
        }


        

        /// <summary>
        /// Gets the k closest nodes to a given person
        /// </summary>
        /// <param name="person">Person</param>
        /// <returns>k closest nodes</returns>
        public KClosest GetClosest(Person person)
        {            
            SortedList<BigInteger, Person> list = new SortedList<BigInteger, Person>();

            KTree iter = this.GetTree(person.Hash);
            KBucket buc = iter.bucket;
            
            foreach (Person p in buc)
            {
                list.Add(KClosest.CalculateDistance(p.Hash, person.Hash),p);
            }         
            KClosest closest = new KClosest(person.Hash,list);

            if (closest.Count() == KBucket.K)
                return closest;

            bool b = false;

            KTree father = iter.father, sun = (iter.bucket.Bit)? iter.left : iter.right;
            do
            {
                if (father!=null)
                {
                    b = closest.AddAll(KClosest.ToKClosest(person.Hash, father.bucket));
                    father = father.father; 
                }
                else b = false;

                if (sun!=null)
                {
                    b = closest.AddAll(KClosest.ToKClosest(person.Hash, sun.bucket)) || b;
                    sun = (sun.bucket.Bit) ? sun.left : sun.right;
                }
            }while(b);

            return closest;
        }

        /// <summary>
        /// Removes a person from the structure
        /// </summary>
        /// <param name="person">Person to remove</param>
        public void Remove(Person person)
        {
            this.GetKBucket(person).Remove(person);
        }
        #endregion
    }
}
